package __1背包

/*
*
原题链接:
https://leetcode.cn/problems/partition-equal-subset-sum/

代码随想录 动态规划章节
416. 分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

416. 分割等和子集
给你一个 只包含正整数的非空数组nums. 请你判断是否可以将这个数组分割为两个子集， 使得两个子集的元素和相等。
那就计算总和的一半是多少呗

看看能不能使用数组种的数组，凑出总和值一半的大小
创建dp数组,dp[j]表示目标为target重量的位置，能组成的最大数量是多少

递推公式: dp[j] = dp[j]

思路:
每个物品只能使用一次, 为0-1背包问题
回归主题: 首先, 本题要求集合能否出现总和为 sum/2的子集

只有确定了如下四点, 才能把0-1背包问题套用到本题上
  - 背包的体积为 sum / 2
  - 背包要放入的商品(集合里的元素) 重量为元素的数值, 价值也为元素的数组
  - 背包如果正好装满, 说明找到了总和为 sum / 2的子集
  - 背包中每一个元素是不可重复放入

以上分析完, 就可以套用0-1背包, 来解决这个问题了.

一. 确定dp数组含义
  - dp[j]: 容量为j的背包, 所背的物品的最大价值为dp[j]

二. 递推公式
  - 0-1背包递推公式: dp[j] = max(dp[j], dp[j-weight[i]]+value[i])  //放入当前物品还是不放入当前物品

三. 初始化
  - 从dp[j]定义看, dp[0] = 0, 其它非零下标也初始化为0即可

四. 遍历顺序
  - 先遍历物品, 后遍历背包

五. 打印dp数组
*/
func canPartition(nums []int) bool {
	sum := 0
	for _, num := range nums {
		sum += num
	}
	// 如果 nums 的总和为奇数则不可能平分成两个子集
	if sum%2 == 1 {
		return false
	}

	target := sum / 2
	dp := make([]int, target+1) //dp[j]: 容量为j的背包, 最多能装多少重量的物品  (0索引废弃)

	for _, num := range nums { //先遍历物品
		for j := target; j >= num; j-- { //遍历背包, 需要倒序遍历
			dp[j] = max(dp[j], dp[j-num]+num)
		}
	}

	return dp[target] == target
}
